import time
import matplotlib.pyplot as plt
from alg import SolutionBruteForce, SolutionDivideAndConquer, SolutionDP
import random
import matplotlib

matplotlib.rcParams['font.sans-serif'] = ['SimHei']
matplotlib.rcParams['axes.unicode_minus'] = False

def benchmark_algorithms():
    ns = [10, 20, 40, 80, 160, 320, 640]  # 暴力算法太慢，n 不宜太大
    times_brute = []
    times_divide = []
    times_dp = []

    for n in ns:
        nums = [random.randint(-1000, 1000) for _ in range(n)]

        # 正确性测试
        res_brute = SolutionBruteForce().maxSubArray(nums)
        res_divide = SolutionDivideAndConquer().maxSubArray(nums)
        res_dp = SolutionDP().maxSubArray(nums)
        if not (res_brute == res_divide == res_dp):
            print(f"结果不一致！n={n}，Brute={res_brute}，Divide={res_divide}，DP={res_dp}")
            return

        # 计时
        start = time.time()
        SolutionBruteForce().maxSubArray(nums)
        times_brute.append(time.time() - start)

        start = time.time()
        SolutionDivideAndConquer().maxSubArray(nums)
        times_divide.append(time.time() - start)

        start = time.time()
        SolutionDP().maxSubArray(nums)
        times_dp.append(time.time() - start)

    plt.figure(figsize=(8, 5))
    plt.plot(ns, times_brute, '-', label='Brute Force $O(n^2)$', color='red')
    plt.plot(ns, times_divide, '-', label='Divide & Conquer $O(n\\log n)$', color='blue')
    plt.plot(ns, times_dp, '-', label='DP $O(n)$', color='green')
    plt.xlabel('输入规模 n')
    plt.ylabel('运行时间 (秒)')
    plt.title('三种算法实际运行时间对比')
    plt.legend()
    plt.grid(True)
    plt.savefig('runtime_vs_n.png')
    plt.show()

if __name__ == "__main__":
    benchmark_algorithms() 